package edu.whu.rose.clock.kps.algorithm.blinks.search2;

import java.io.UnsupportedEncodingException;
import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

import com.sleepycat.je.DatabaseException;

import edu.whu.rose.clock.kps.algorithm.blinks.index.BilevelIndexDB;
import edu.whu.rose.clock.kps.algorithm.blinks.index.BlockVertexKeyword;
import edu.whu.rose.clock.kps.algorithm.blinks.index.KNEntry;
import edu.whu.rose.clock.kps.algorithm.blinks.index.NKEntry;
import edu.whu.rose.clock.kps.datastruct.SimpleAnswer;
import edu.whu.rose.clock.kps.datastruct.SimpleSubgraphVertex;
import edu.whu.rose.clock.ssql.util.ExpandableIntArray;
import edu.whu.rose.clock.ssql.util.MyMath;
import edu.whu.rose.clock.ssql.util.SequentialIntArray;

public class BiLevelSearch2 {

	private BilevelIndexDB bidb;
	
	private double bound;
	
	public long totalTime;
	public long indexTime;
	
	public BiLevelSearch2(BilevelIndexDB bidb) {
		this.bidb = bidb;
	}
	
	public static void main(String[] args) {
		BilevelIndexDB bidb = new BilevelIndexDB();
		if (bidb.initEnv() && bidb.openDB()) {
			BiLevelSearch2 blinks = new BiLevelSearch2(bidb);
			String[] keywords = new String[]{"schema", "reuse"};
			int k = 100;
			
			for (int w = 0; w < 5; w++) {
				blinks.indexTime = 0l;
				SimpleAnswer[] answers = blinks.process(keywords, k);
				
				
				if (answers != null) {
					double sum = 0.0d;
					int i = 0;
					for (; i < answers.length; i++) {
						SimpleAnswer sa = answers[i];
						System.out.print("Rank " + (i + 1) + ": {" + sa.getScore() + "} ");
						System.out.print(" root[" + sa.getRoot() + "] ");
						sum += sa.getScore();
						for (int y = 0; y < sa.getLeafNumber(); y++) {
							int[] path = sa.getPath(y);
							System.out.print("( ");
							if (path != null) {
								for (int m = 0; m < path.length; m++) {
									System.out.print(path[m] + ", ");
								}
							}
							System.out.print(" )");
						}
						System.out.println();
					}
					if (i == 0) {
						System.out.println("Sorry, no result is found.");
					}
					else {
						System.out.println("Average score: " + (sum / Math.min(k, i)));
					}

					System.out.println("Time exhausted for reading index: " + blinks.indexTime + "ms");
					System.out.println("Time exhausted for searching: " + blinks.totalTime + " ms");
				}
				else {
					System.out.println("Sorry, no result is found.");
				}
			}
			
			bidb.closeDB();
		}
	}
	
	public SimpleAnswer[] process(String[] keywords, int k) {
		Date startTime = new Date();
		SimpleAnswer[] topk = new SimpleAnswer[k];
		
		try {
			int size = 0;
			
			GroupHeap2[] heaps = new GroupHeap2[keywords.length];
			
			HashMap<Integer, PotentialTree2> trees = new HashMap<Integer, PotentialTree2>();
			
			ArrayList<HashSet<Integer>> crossed = new ArrayList<HashSet<Integer>>();
			for (int i = 0; i < keywords.length; i++) {
				crossed.add(new HashSet<Integer>());
			}
			
			HashSet<Integer> abandoned = new HashSet<Integer>();
			HashSet<Integer> rest = new HashSet<Integer>();
			
			int visitTime = 0;
			int repeatTime = 0;
			
			bound = Double.MAX_VALUE;
			boolean overBound = false;
			
			boolean first_k = true;
			
			Date date = null;
			
			// initialize heaps
			for (int i = 0; i < keywords.length; i++) {
				heaps[i] = new GroupHeap2();
				date = new Date();
				int[] blockIds = bidb.getFromKeywordBlock(keywords[i]);
				indexTime += new Date().getTime() - date.getTime();
				for (int j = 0; j < blockIds.length; j++) {
					date = new Date();
					KNCursor2 knc = new KNCursor2(blockIds[j], bidb, keywords[i]);
					indexTime += new Date().getTime() - date.getTime();
					heaps[i].enqueue(knc);
				}
			}
			
			while (true) {
				// expand group by group
				for (int i = 0; i < keywords.length; i++) {
					Cursor2 cursor = heaps[i].dequeue();
					cursor.next();

					int block = cursor.getBlock();
					double distance = cursor.getDistance();
					int vertex = cursor.getNode();
					int first = cursor.getFirst();
					
					Integer Root = new Integer(vertex);
					
					// put the cursor back to heap if it is not empty
					if (!cursor.empty()) {
						heaps[i].enqueue(cursor);
					}
					
					// visit current root
					visitTime++;
					boolean mark = true;
					PotentialTree2 tree = trees.get(Root);

//					if (vertex == 115426) {
//						System.out.println();
//					}

					// do not visit this root if it has been abandoned
					if (abandoned.contains(Root)) {
						if (tree.getDistance(i) == Double.MAX_VALUE) {
							tree.setPredecessor(i, first);
						}
						continue;
					}
					
					// the tree does not exist
					// produce a new tree at this root, and try forward connection to other group in this block
					if (tree == null) {
						tree = new PotentialTree2(vertex, keywords.length);
						tree.setDistance(i, distance);
						tree.setPredecessor(i, first);
						// try to look forward
						date = new Date();
						double np = bidb.getFromVertexPortal(new SimpleSubgraphVertex(block, vertex));
						indexTime += new Date().getTime() - date.getTime();
						for (int j = 0; j < keywords.length; j++) {
							if (j != i) {
								double nk = 0.0d;
								NKEntry nke = null;
								try {
									date = new Date();
									nke = bidb.getFromVertexKeyword(new BlockVertexKeyword(block, vertex, keywords[j]));
									indexTime += new Date().getTime() - date.getTime();
									if (nke != null) {
										nk = nke.getDistance();
										if (np >= nk) { // the shortest path from root to keywords[j] is found
											tree.setDistance(j, nk);
											tree.setPredecessor(j, nke.getFirst());
											tree.setOriginBlock(block);
											tree.setD2(j, nk);
										}
										else {
											tree.setD2(j, np);
										}
									}
								}
								catch (DatabaseException ex) {
									ex.printStackTrace();
								}
							}
						}
						
						trees.put(Root, tree); // put the tree into the forest
						rest.add(Root); // put the root into known vertex set
					}
					// the tree exists, but is over large and so will be abandoned
					else if (bound < Double.MAX_VALUE && sumLBD(tree, heaps, block, keywords) >= bound) {
						// update the shortest path from this root to keywords[i]
						tree.setDistance(i, distance);
						tree.setPredecessor(i, first);
						// abandon the tree
						abandoned.add(Root);
						rest.remove(Root);
						continue;
					}
					// the tree exists and is not over large, and has not been visited by this group
					else if (tree.getDistance(i) == Double.MAX_VALUE) {
						// update the shortest path from this root to keywords[i]
						tree.setDistance(i, distance);
						tree.setPredecessor(i, first);
					}
					// the tree exists and is not over large, but has been visited by this group
					else {
						// do nothing
						mark = false;
						repeatTime++;
					}

					if (mark) { // the tree has been inserted or modified
						if (tree.isAnswer()) { // the tree is a new answer
							if (size < k || tree.sumDistances() < topk[k - 1].getScore()) {
								
//								if (vertex == 113607) {
//									System.out.println();
//								}
								
								SimpleAnswer newAnswer = convert(tree, trees, keywords); // convert the tree to answer
								size = addTopKAnswer(newAnswer, topk, size); // add the answer to top-k
							}
							
							// abandon the tree, since we only allow single tree rooted at this vertex
							abandoned.add(Root);
							rest.remove(Root);

							if (size == k) {
								if (first_k) { // this is the first time we have k answers
									Date firstk = new Date();
//									System.out.println("Time exhausted for reading index: " + indexTime + "ms");
									System.out.println(
											"Time exhausted for producing first k answers: " + 
											(firstk.getTime() - startTime.getTime() - indexTime) + "ms");
									double sum = 0.0d;
									for (int n = 0; n < topk.length; n++) {
										SimpleAnswer sa = topk[n];
										System.out.print("Rank " + (n + 1) + ": {" + sa.getScore() + "} ");
										System.out.print(" root[" + sa.getRoot() + "] ");
										sum += sa.getScore();
										for (int y = 0; y < sa.getLeafNumber(); y++) {
											int[] path = sa.getPath(y);
											System.out.print("( ");
											if (path != null) {
												for (int m = 0; m < path.length; m++) {
													System.out.print(path[m] + ", ");
												}
											}
											System.out.print(" )");
										}
										System.out.println();
									}
									System.out.println("Average score: " + (sum / k));
									first_k = false;
								}
								bound = topk[k - 1].getScore();
							}
						}
					}
					
					// process for crossing blocks
					if (!crossed.get(i).contains(Root)) { // this root has not been crossed as a portal
						date = new Date();
						int[] PBList = bidb.getFromPortalBlock(vertex);
						indexTime += new Date().getTime() - date.getTime();
						if (PBList != null) { // this root is indeed a portal
							crossed.get(i).add(Root); // mark that it is crossed
							if (distance != 0.0d) { // if this root is not a matched vertex
								for (int j = 0; j < PBList.length; j++) { // for each block this portal connects
									int ablock = PBList[j];
									if (ablock != block) { // if the block is not current block
										date = new Date();
										PNCursor2 pnc = new PNCursor2(ablock, bidb, vertex, distance);
										indexTime += new Date().getTime() - date.getTime();
										if (!pnc.empty()) {
											heaps[i].enqueue(pnc); // add a new PN cursor
										}
									}
								}
							}
						}
					}
					
					// check if algorithm can be stopped
					if (size < k) {
						continue;
					}
					
					// condition 1: trees rooted at never-visited vertexes are all larger than the bound
					if (!overBound) {
						double total = 0.0d;
						for (int j = 0; j < keywords.length; j++) {
							double top = heaps[j].top();
							if (top != -1.0d) {
								total += top;
							}
						}
						if (total >= bound) {
							overBound = true;
						}
					}
					
					if (overBound) {
						// condition 2: trees rooted at already-visited vertexes have 
						// lower bounds larger than the bound
						Iterator<Integer> it = rest.iterator();
						while (it.hasNext()) {
							Integer root = it.next();
							PotentialTree2 pt = trees.get(root);
							if (sumLBD(pt, heaps, block, keywords) < bound) {
								break;
							}
							else {
								abandoned.add(root);
								it.remove();
							}
						}
						if (rest.size() > 0) {
							continue;
						}
	
						// stopping the algorithm
						Date endTime = new Date();
						totalTime = endTime.getTime() - startTime.getTime() - indexTime;
						
						return topk;
					}
				}
			}
		}
		catch (DatabaseException ex) {
			ex.printStackTrace();
		}
		catch (UnsupportedEncodingException ex) {
			ex.printStackTrace();
		}
		
		// finish all
		Date endTime = new Date();
		totalTime = endTime.getTime() - startTime.getTime() - indexTime;
		
		return topk;
	}
	
	private SimpleAnswer convert(PotentialTree2 pt, HashMap<Integer, PotentialTree2> trees, String[] keywords) {
		int root = pt.getRoot();
		
		if (root == 173882) {
			System.out.println();
		}
		
		int[] leaves = new int[pt.size()];
		int[][] paths = new int[pt.size()][];
		SequentialIntArray allVertexes = new SequentialIntArray();
		allVertexes.insert(root);
		
		for (int i = 0; i < pt.size(); i++) {
			paths[i] = getPath(i, pt, keywords, allVertexes, trees);
			if (paths[i] == null) {
				leaves[i] = root;
			}
			else {
				leaves[i] = paths[i][paths[i].length - 1];
			}
		}
		
		return new SimpleAnswer(root, leaves, paths, allVertexes.getArray());
	}
	
	private int[] getPath(int i, PotentialTree2 pt, String[] keywords,
			SequentialIntArray allVertexes, HashMap<Integer, PotentialTree2> trees) {
		ExpandableIntArray eia = new ExpandableIntArray();
		PotentialTree2 current = pt;
		int block = current.getOriginBlock();

//		if (block == 0) {
//			System.out.println();
//		}
		
		
		int first = 0;
		while (current != null) {
			first = current.getPredecessor(i);

			if (first == 115426 && i == 0) {
				System.out.println();
			}
			
			if (first == 0) {
				System.err.println("Error: predecessor of " + current.getRoot() + " for group " + i + " not found");
				System.exit(1);
//				break;
			}
			else if (first != -1) {
				allVertexes.insert(first);
				eia.add(first);
				current = trees.get(new Integer(first));
			}
			else {
				return eia.toArray();
			}
		}

		Date date = new Date();
		KNCursor2 knc = new KNCursor2(block, bidb, keywords[i]);
		indexTime += new Date().getTime() - date.getTime();
		
		KNEntry[] list = (KNEntry[]) knc.getList();
		for (int j = list.length - 1; j >= 0; j--) {
			if (list[j].getNode() == first) {
				first = list[j].getFirst();
				
				if (first == -1) {
					return eia.toArray();
				}
				else {
					eia.add(first);
					allVertexes.insert(first);
				}
			}
		}
		
//		System.err.println("Error: path from " + current.getRoot() + " to group " + i + " not found");
		
		return eia.toArray();
	}
	
	private double sumLBD(PotentialTree2 tree, GroupHeap2[] heaps, int block, String[] keywords) {
		double sum = 0.0d;
		for (int i = 0; i < tree.size(); i++) {
			double distance = tree.getDistance(i);
			if (distance < Double.MAX_VALUE) {
				sum += distance;
			}
			else {
				double d1 = 0.0d;
				if (!heaps[i].isEmpty()) {
					d1 = heaps[i].top();
				}
				else {
					return Double.MAX_VALUE;
				}
				double d2 = tree.getD2(i);
				if (d2 == Double.MAX_VALUE) {
					return Double.MAX_VALUE;
				}
				double d = Math.max(d1, d2);
				sum += d;
			}
		}
		return sum;
	}

	private int addTopKAnswer(SimpleAnswer answer, SimpleAnswer[] topk, int size) {
		int pos = -1;
		boolean inserted = false;
		for (int i = 0; i < size; i++) {
			int x = answer.compare(topk[i]);
			if (x == MyMath.ARR1_CONTAIN_ARR2) {
				return size;
			}
			else if (x == MyMath.ARR2_CONTAIN_ARR1) {
				if (!inserted) {
					for (int j = i; j > pos + 1; j--) {
						topk[j] = topk[j - 1];
					}
					topk[pos + 1] = answer;
					inserted = true;
				}
				else {
					for (int j = i; j < size - 1; j++) {
						topk[j] = topk[j + 1];
					}
					size--;
				}
			}
			else if (x == MyMath.ARR1_EQUAL_ARR2) {
				if (answer.getScore() < topk[i].getScore()) {
					for (int j = i; j > pos + 1; j--) {
						topk[j] = topk[j - 1];
					}
					topk[pos + 1] = answer;
					return size;
				}
				else {
					return size;
				}
			}
			
			if (answer.getScore() >= topk[i].getScore()) {
				pos = i;
			}
		}
		
		if (inserted) {
			return size;
		}
		
		if (pos < size - 1) {
			if (size < topk.length) {
				for (int i = size; i > pos + 1; i--) {
					topk[i] = topk[i - 1];
				}
				size++;
			}
			else {
				for (int i = topk.length - 1; i > pos + 1; i--) {
					topk[i] = topk[i - 1];
				}
			}
			topk[pos + 1] = answer;
		}
		else if (size < topk.length) {
			topk[size] = answer;
			size++;
		}
		
		return size;
	}

}
